package com.SingleLinkedList;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //创建结点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        //创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addNodeByOrder(hero1);
        singleLinkedList.addNodeByOrder(hero4);
        singleLinkedList.addNodeByOrder(hero3);
        singleLinkedList.showLinkedList();

        System.out.println("当前链表有效结点个数为："+getLength(singleLinkedList.getHead()));
        System.out.println(getLastIndexNode(singleLinkedList.getHead(), 4));
//        covertLinkedList(singleLinkedList.getHead());
//        singleLinkedList.showLinkedList();
        recoverPrintList(singleLinkedList.getHead());
    }


    /**
     * 1.求单链表结点的个数，带头结点的链表，头结点不计数
     * @param head 链表头结点
     * @return 返回结点个数
     */
    public static int getLength(HeroNode head){
        int count = 0;
        HeroNode temp = head;
        while (temp.next != null){
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 查找单链表中倒数第index个结点，转换成正序
     * @param head 接受head遍历链表求出链表长度length
     * @param index 倒数第index个结点
     * @return 第length-index个结点
     */
    public static HeroNode getLastIndexNode(HeroNode head,int index){
        //如果量表为空，则直接返回空
        if(head.next == null){
            return null;
        }
        int length = getLength(head);
        if(length < index || index <= 0){
            System.out.println("输入无效");
            return null;
        }else {
            HeroNode temp = head;
            for(int i = 0;i<length-index+1;i++){
                temp = temp.next;
            }
            return temp;
        }
    }
    /*
    思路：创建一个新的头结点newHead。根据传入的头结点从头到尾遍历链表，遍历链表的同时用”头插法“将结点插入到新链表中，再将head.next = newHead.next
    总结：链表的改动只需要围绕头结点进行操作，创建新的头结点即是一个新的链表(而不是直接new一个新链表。
     */

    /**
     * 单链表反转
     * @param head
     */
    public static void covertLinkedList(HeroNode head){
        //如果链表为空或只有一个结点时，无需反转
        if(head.next == null || head.next.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        HeroNode next = null; //用于指向当前结点[temp]的下一个结点
        HeroNode newHead = new HeroNode();
        while(temp  != null){
            /*
            temp.next = newHead.next;
            newHead.next = temp;
            temp = temp.next;

            出现错误：第一句和第三句使得插入第一个结点时，temp = temp.next = newHead.next = null
            原本的链表被断开，需要引入中间变量保存下一个结点
             */
            next = temp.next;
            temp.next = newHead.next;
            newHead.next = temp;
            temp = next;

        }
        head.next = newHead.next;
    }
    /*
    从尾到头打印单链表
    思路：1) 将单链表反转后打印
            问题：破坏了原本链表结构
         2) 循环遍历链表时将各节点入栈后再出栈，后进先出实现逆序打印
    总结：涉及到从后到前的顺序都可以考虑用<栈>来处理
     */
    public static void recoverPrintList(HeroNode head){
        //链表为空时直接结束
        if(head.next == null){
            return;
        }
        HeroNode temp = head.next;
        Stack<HeroNode> stack = new Stack<>();
        while (temp != null){
            stack.add(temp);
            temp = temp.next;
        }
        //循环结束以后即遍历到最后一个结点，所有结点全部入栈
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
    /*
    将两个有序单向链表合并
     */
    public void mergerList(HeroNode head1,HeroNode head2){

        //判断两个链表是否含有空链表
        if(head1.next == null || head2.next == null){
            System.out.println("两个链表含有空链表");
            return;
        }
        //合并链表时参数产生新的头结点
        HeroNode newHead = new HeroNode();
        HeroNode temp1 = head1;
        HeroNode temp2 = head2;
        HeroNode res = null;
        while(temp1.next != null){
            res = temp1.next;
            while(temp2.next != null){
                if(temp1.next.no <= temp2.next.no){
                    temp1.next.next = temp2.next;
                    temp2.next = temp1.next;
                    break;
                }
                temp2 = temp2.next;
            }
            temp1 = res;
        }

    }

}
